#include <bits/stdc++.h>
using namespace std;
class Solution1
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + nums[i - 1];
        int ret = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                int tem = sum[j] - sum[i - 1];
                // if(tem<0) continue;
                if (tem == 0 || tem % k == 0)
                {
                    cout << i << ":" << j << " " << tem << endl;
                    ret++;
                }
            }
        }
        return ret;
    }
};

//(sum[j] - sum[i]) % k == 0，那么 sum[j] % k == sum[i] % k
class Solution1
{
public:
    int subarraysDivByK(vector<int> &nums, int k)
    {
        int n = nums.size();
        vector<int> sum(n + 1, 0);
        for (int i = 1; i <= n; i++)
            sum[i] = sum[i - 1] + nums[i - 1];
        int ret = 0;

        unordered_map<int,int>m;
        m[0]=1;//数组为0个元素 此时的和就是0 此时的余数就是0
        for(int i=1;i<=n;i++)
        {
           int tem=(sum[i]%k+k)%k;
           if(m.find(tem)!=m.end())
           {
            ret+=m[tem];
           }
            m[tem]++;
        }
        return ret;
    }
};